package dp.prevClass.exer01;

import java.util.Scanner;

/**
 * 题目描述：
 * 一家公司购买长钢条，将其切割成短钢条出售，切割本身没有成本，长度为i的短钢条的价格为Pi。那给
 * 定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。
 * 输入要求：
 * 输入钢条的长度n。
 * 输出要求：
 * 输出获得的最大收益
 */
public class Main {

    private static final int LENGTH = 10;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] weight = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] value = new int[] {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        int n = scanner.nextInt();
        int[][] dp = new int[LENGTH + 1][n + 1];
        for (int i = 1; i <= LENGTH; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - weight[i - 1] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], value[i - 1] + dp[i][j - weight[i - 1]]);
                }
            }
        }
        System.out.println(dp[LENGTH][n]);
    }
}
